{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "shortest.ipynb\n",
    "----------------\n",
    "\n",
    "Given a mesh and two vertex indices find the shortest path\n",
    "between the two vertices while only traveling along edges\n",
    "of the mesh.\n",
    "\"\"\"\n",
    "\n",
    "import trimesh\n",
    "import numpy as np\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test on a sphere mesh\n",
    "mesh = trimesh.primitives.Sphere()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edges without duplication\n",
    "edges = mesh.edges_unique"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the actual length of each unique edge\n",
    "length = mesh.edges_unique_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create the graph with edge attributes for length\n",
    "g = nx.Graph()\n",
    "for edge, L in zip(edges, length):\n",
    "    g.add_edge(*edge, length=L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# arbitrary indices of mesh.vertices to test with\n",
    "start = 0\n",
    "end = int(len(mesh.vertices) / 2.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# run the shortest path query using length for edge weight\n",
    "path = nx.shortest_path(g,\n",
    "                        source=start,\n",
    "                        target=end,\n",
    "                        weight='length')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# VISUALIZE RESULT\n",
    "# make the sphere white\n",
    "mesh.visual.face_colors = [255,255,255,255]\n",
    "# Path3D with the path between the points\n",
    "path_visual = trimesh.load_path(mesh.vertices[path])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a scene with the mesh, path, and points\n",
    "scene = trimesh.Scene([path_visual, mesh ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scene.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
